package com.kobeliu.entity;

/**
 * leetCode 240
 *
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 示例:
 *
 * 现有矩阵 matrix 如下：
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * 给定 target = 5，返回 true
 * 给定 target = 20，返回 false。
 */

public class Demo_36_No240 {

    public static void main(String[] args) {
        int[][] nums =new int[][] {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(findNumberIn2DArray(nums,5));
    }

    public static boolean findNumberIn2DArray ( int[][] matrix, int target){

        int temp = 0; //现在到第几行了
        int low = matrix.length; //总行数
        if (low == 0) return false; //做判断 否则 right可能越界
        int left = 0; //左指针
        int right = matrix[0].length - 1; //右指针
        int mid = 0;

        while (temp < low) {
            while (left <= right) {
                mid = left + ((right - left) >> 1);
                if (matrix[temp][mid] > target) {
                    right = mid - 1;
                } else if (matrix[temp][mid] < target) {
                    left = mid + 1;
                } else {
                    return true;
                }
            }
            //出来代表一轮结束了
            temp++;
            if (temp < low) {
                left = 0;
                right = matrix[temp].length - 1;
            }
        }
        return false;

    }

}
